﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QCodeLib.DataStructure
{
    public class Sort
    {
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="array"></param>
        public static void BubbleSort(int[] array)
        {
            int temp = 0;
            //首循环 由头至尾
            for (int i = 0; i < array.Length - 1; i++)
            {
                //再循环 从i+1 至 尾
                for (int j = i + 1; j < array.Length; j++)
                {
                    //大的放后面 降序
                    if (array[j] < array[i])
                    {
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        public static void QuickSort(int[] nums, int left, int right)
        {
            //大前提 左边 < 右边
            if (left < right)
            {
                int i = left;
                int j = right - 1;
                int middle = nums[(left + right) / 2];
                while (true)
                {
                    //左边i < 右边 并且 数字[i] < 中间值 继续 i++
                    while (i < right && nums[i] < middle) { i++; };
                    //右边j >0 并且 数字[j] > 中间值 继续 j--
                    while (j > 0 && nums[j] > middle) { j--; };
                    //循环结束
                    if (i == j) break;

                    int temp;
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    if (nums[i] == nums[j]) j--;
                }
                QuickSort(nums, left, i);
                QuickSort(nums, i + 1, right);
            }


        }
    }
}
